Field of the Invention
The present invention relates to a system and method for providing fairness and countering flow starvation in asynchronous wireless networks in which all nodes are not necessarily mutually within radio range, i.e., “multi-hop” wireless networks.
Brief Description of the Related Art
The IEEE 802.11 standard family represents the state of the art of asynchronous random access mechanisms. The standard adopts Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) at the Medium Access Control (MAC) layer and consequently targets (within a clique) having a single flow exclusively capture the medium while other flows defer their transmissions as shown in FIG. 1(b). In multi-hop networks, nodes are not within range of each other, hence, nodes have differing channel states. Such asymmetric channel states can result in a backlogged flow capturing the system resources and causing other flow(s) to persistently receive very low throughput. See M. Garetto, T. Salonidis, and E. Knightly, “Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks,” Proceedings of IEEE INFOCOM '06, Barcelona, Spain, April 2006.
Consider the multi-hop topology shown in FIG. 2(a), node B, the transmitter of flow Bb, knows when to contend for the medium because it overhears the activity of flow Aa. On the other hand, node A, the transmitter of flow Aa, has no information about flow Bb and must blindly contend for the medium. The probability of successful transmission of flow Aa packets is close to zero. Similarly, the middle flow Aa in FIG. 2(b) will receive very low throughput compared to the outer flows Bb and Cc. Transmitter A will find the medium busy with high probability due to the uncoordinated transmissions of flows Bb and Cc.
The upcoming IEEE 802.11n Multiple-Input Multiple-Output (MIMO) standard promises performance gains compared to Single-Input Single-Output (SISO) systems by utilizing spatial diversity (increasing link reliability, reducing transmission power, or equivalently, extending the transmission range) or spatial multiplexing (increasing link capacity). However, because the MIMO physical layer employs CSMA/CA at the MAC layer, the 802.11n standard and its variants will suffer from the same severe unfairness and starvation problems encountered in single antenna networks. See M. Garetto, T. Salonidis, and E. Knightly, “Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks,” Proceedings of IEEE INFOCOM '06, Barcelona, Spain, April 2006. Indeed, it can be shown experimentally using pre-802.11n devices that MIMO worsens unfairness in key starvation scenarios. Such CSMA/CA starvation is attributed to the asymmetric and incomplete views of the wireless channel for contending flows in multi-hop networks. Use of MIMO simply to improve the performance of individual links provides a further advantage to the winning flows.
Multiple transmit and receive antennas can also be used for beamforming (also called stream control) and interference cancellation, respectively. Thus, in contrast to the IEEE 802.11 standards, multiple simultaneous transmissions can coexist in the same channel. However, protocols employing these mechanisms require network-wide synchronization and channel information of all interfering transmitters at each receiver in order to null out their signals. See P. Casari, M. Levorato, and M. Zorzi, “DSMA: an access method for MIMO ad hoc networks based on distributed scheduling,” Proceedings of ACM IWCMC, Vancouver, Canada, July 2006; M. Park, S.-H. Choi, and S. M. Nettles, “Cross-layer MAC design for wireless networks using MIMO,” Proceedings of IEEE Globecom '05, December 2005; M. Park, R. J. Heath, and S. Nettles, “Improving throughput and fairness for MIMO ad hoc networks using antenna selection diversity,” Proceedings of IEEE Globecom '04, December 2004; K. Sundaresan, R. Sivakumar, M. Ingram, and T.-Y. Chang, “A fair medium access control protocol for ad-hoc networks with MIMO links,” Proceedings of IEEE INFOCOM '04, Hong Kong, March 2004; K. Sundaresan and R. Sivakumar, “A unified MAC framework for ad-hoc networks with smart antennas,” in Proceedings of ACM Mobihoc '04, Tokyo, Japan, May 2004; R. Bhatia and L. Li, “Throughput optimization of wireless mesh networks with mimo links,” Proceedings of IEEE INFOCOM '07, Anchorage, Ak., May 2007; and A. Ashtaiwi and H. Hassanein, “Rate splitting mimo-based mac protocol,” in Proceedings of IEEE Conference on Local Computer Networks, Dublin, Ireland, October 2007.
While such synchronous MAC protocols address fairness by allowing multiple simultaneous transmissions, the overhead due to network synchronization and channel acquisition significantly degrades the system throughput as was empirically shown in S. Gaur, J.-S. Jiang, M. Ingram, and M. Demirkol, “Interfering MIMO links with stream control and optimal antenna selection,” Proceedings of IEEE Globecom '04, Dallas, Tex., November 2004.
To demonstrate the existence of starvation in MIMO networks, we designed the following experiment. We utilized four laptops, each equipped with a wireless Belkin card that utilizes the Ralink RT2860 and RT2820 chipsets. The cards fully comply with the current IEEE 802.11n draft with backward compatibility with the IEEE 802.11b/g standards. The chipset embodies a 2 transmitter, 3 receiver (2T3R) architecture 1 via on-board dipole antennas with 1 dBi antenna gain. We configured the cards in the 802.11n 40 MHz mode with only 802.11b compatibility. We used iperf to generate fully backlogged UDP traffic sessions at transmitting nodes. We arranged the four nodes to form two contending transmitter-receiver pairs in 2 different indoor topologies: a fully-connected topology in which all nodes are within range of each other, and the information asymmetry topology shown in FIG. 2(a), in which the transmitter of one flow is out of range of both the sender and the receiver of the other flow.
FIG. 3 depicts the throughput (averaged over 10 measurements, each of length 120 seconds) of each flow in both setups when the RTS/CTS mechanism is both disabled and enabled. While the two flows fairly shared the available bandwidth in the fully-connected scenario, one flow received 68.34 times the throughput of the other flow in 802.11n networks in the information asymmetry topology when the RTS/CTS handshake was disabled. This throughput ratio dropped to 12.14 when we repeated the same experiment with 802.11b cards, as shown in FIG. 4. Thus, MIMO worsened the severity of starvation since the flow which exclusively captured the medium transmitted at a higher rate compared to the SISO case. Enabling the RTS/CTS handshake did not alleviate starvation, but rather degraded the throughput due to the transmission of such control packets at the base rate.